package com.nanxhs;

import java.util.ArrayList;
import java.util.List;

/**
 *  二分查找算法
 *
 * @author: haibin.tang
 * @date: 2021/2/1
 */
public class BinarySearch {
    /**
     * 查找次数
     */
    private static final ThreadLocal<Integer> SEARCH_COUNT = ThreadLocal.withInitial(()-> 0);

    /**
     *  查找
     * @param dataList  数据列表
     * @param target 查找目标值
     * @return
     */
    public static int search(List<Integer> dataList, int target) {
        return search(dataList, target, 0, dataList.size());
    }

    /**
     *  执行查找具体事项, 递归
     * @param dataList 数据列表
     * @param target 查找目标值
     * @param start 起始查找位置
     * @param end 结束查找位置
     * @return  返回下标，如果未找到返回-1
     */
    private static int search(List<Integer> dataList, int target, int start, int end) {
        int mid = (start + end) / 2;
        if (mid == dataList.size() || mid == 0) {
            return -1;
        }
        SEARCH_COUNT.set(SEARCH_COUNT.get() + 1);
        int midData = dataList.get(mid);
        if (midData == target) {
            return mid;
        }
        return midData < target ? search(dataList, target, mid + 1, end) : search(dataList, target, start, mid - 1);
    }

    public static void main(String[] args) {
        int size = 1024;
        List<Integer> codeList = new ArrayList<>(size);
        for (int index = 1; index <= size; ++index) {
            codeList.add(index);
        }
        int index = search(codeList, 1025);
        System.out.println("总查找次数" + SEARCH_COUNT.get() + ", " + (index == -1 ? "未找到元素" : "该元素处于下标 [" + index + "]"));
    }
}